package leetcode.weekly.week321;

import java.util.Deque;
import java.util.LinkedList;

import leetcode.helper.tree.ListNode;

//Solution3Test
public class Solution3 {

	public ListNode removeNodes(ListNode head) {
		Deque<ListNode> stack = new LinkedList<>();
		while (head != null) {
			while (!stack.isEmpty() && stack.peekLast().val < head.val) {
				stack.pollLast();
			}
			stack.add(head);
			head = head.next;
		}
		ListNode ans = new ListNode();
		ListNode p = ans;
		while (!stack.isEmpty()) {
			p.next = stack.poll();
			p = p.next;
		}
		p.next = null;
		return ans.next;
	}
}
